//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复
//的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例： 
//
// 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
// 
// Related Topics 数组 双指针 
// 👍 2487 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.*;

//Java：三数之和
public class P15ThreeSum {
    public static void main(String[] args) {
        Solution solution = new P15ThreeSum().new Solution();
        // TO TEST
        //int[] input={-1, 0, 1, 2, -1, -4};
        int[] input={0,0,0,0};
        List<List<Integer>> res= solution.threeSum(input);

        for (List<Integer> list:res){
            for(int x:list){
                System.out.print(x+" ");
            }
            System.out.println();
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public List<List<Integer>> res = new ArrayList<>();



        public List<List<Integer>> threeSum(int[] nums) {

            if (nums == null) {
                return res;
            }

            List<Integer> list = new ArrayList<>();
            int len = nums.length;

            Arrays.sort(nums); //进行排序
            for (int i = 0; i < len; i++) {
                if(nums[i]>0){
                    break;
                }
                if(i==0||i>0&&nums[i]!=nums[i-1]){
                    int L=i+1;
                    int R=len-1;

                    while(L<R){
                        int sum=nums[i]+nums[L]+nums[R];
                        if(sum==0){
                            res.add(Arrays.asList(nums[i],nums[L],nums[R]));
                            while(L+1<R&&nums[L]==nums[L+1]){
                                L++;
                            }
                            while(R-1>L&&nums[R]==nums[R-1]){
                                R--;
                            }
                            L++;
                            R--;
                        }else if(sum<0){
                            L++;
                        }else{
                            R--;
                        }
                    }
                }
            }

            return res;
        }

        /*
        *
        * */
        public List<List<Integer>> threeSum1(int[] nums) {
        /*
        -1 0 1 2 -1 -4
        * */

            if (nums == null) {
                return res;
            }

            List<Integer> list = new ArrayList<>();
            int len = nums.length;

            Arrays.sort(nums);
            for (int i = 0; i < len; i++) {
                if(i>0&&nums[i]==nums[i-1]){
                    continue;
                }
                int target = -nums[i];
                twoSum(nums,i+1,len-1,target);
            }

            return res;
        }


        /*
        * 使用map无法解决重复的问题  比如 0 0 0
        * */
        public void twoSum(int[] nums, int begin, int end, int target) {
            if(begin<0||end>=nums.length||begin>end){
                return;
            }
            Map<Integer, Integer> map = new HashMap<>();

            while (begin <= end) {
                int cut = target - nums[begin];
                if (map.containsKey(cut)) {
                    res.add(Arrays.asList(-target,cut,nums[begin]));
                }
                map.put(nums[begin],begin);
                begin++;
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
